package string_question.leecode.test17;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/6 19:31
 */
public class Solution1 {

    // 电话号码映射
    public List<String> letterCombinations(String digits) {
        String[] dic = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> res = new ArrayList<>();
        if (digits.length() > 0) {
            dfs(res, digits.toCharArray(), 0, new StringBuilder(), dic);
        }
        return res;
    }

    // 回溯
    private void dfs(List<String> res, char[] chars, int c, StringBuilder path, String[] dic) {
        if (c == chars.length) {
            res.add(new String(path));
            return;
        }
        String s = dic[chars[c] - '2'];
        for (int i = 0; i < s.length(); i++) {
            path.append(s.charAt(i));
            dfs(res, chars, c + 1, path, dic);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
